package com.mamingchao.issue.KMP;

import org.springframework.util.StringUtils;

import java.util.Arrays;

/**
 * Created by mamingchao on 2024/12/15.
 */
public class KMP {


    /**
     * 基于KMP算法，计算 str2 在str1中出现最早的index 位置
     * Returns the index within this string of the first occurrence of the
     * specified substring.
     * <p>The returned index is the smallest value <i>k</i> for which:
     * <blockquote><pre>
     * this.startsWith(str, <i>k</i>)
     * </pre></blockquote>
     * If no such value of <i>k</i> exists, then {@code -1} is returned.
     * @param str2 待查找的子串   the substring to search for
     * @param str1 the string which the substring will  search in
     * @return the index of the first occurrence of the specified substring,
     *          or {@code -1} if there is no such occurrence.
     */
    static int indexOf( String str1, String str2){

        if (StringUtils.isEmpty(str1) || StringUtils.isEmpty(str2) || str2.length() > str1.length()){
            return -1;
        }

        char[] str1Arr = str1.toCharArray();
        char[] str2Arr = str2.toCharArray();

        int[] nextArr = getNextArr(str2Arr);

        // str1开始比对的索引位置
        int i = 0;
        // 从str1的i或者str2的0 位置的偏移量
        int offSet = 0;
        while (i + offSet <= str1.length()  && offSet <= str2.length()) {
            if(offSet == str2.length()){ // str2找到了最后一个元素，找到了
                return i;
            } else if (i + offSet == str1.length()) { // str1 找到了头，也没找到
                return -1;
            } else if(str1Arr[i + offSet] == str2Arr[offSet]){
                offSet ++;
            } else if(-1 == nextArr[offSet]) { // 当str2 还在第一个字符
                i++;
            } else {
                // KMP 算法加速过程
                i = i + offSet;
                offSet = nextArr[offSet];
                i = i - offSet;
            }

        }

        return -1;

    }

    /**
     * Optimized KMP implementation to find substring index
     * @param str1 the string to search in
     * @param str2 the substring to search for
     * @return the index of first occurrence of str2 in str1, or -1 if not found
     */
    public static int indexOf2(String str1, String str2) {
        if (StringUtils.isEmpty(str1) || StringUtils.isEmpty(str2) || str2.length() > str1.length()) {
            return -1;
        }

        char[] str1Arr = str1.toCharArray();
        char[] str2Arr = str2.toCharArray();
        int[] next = getNextArr(str2Arr);
        
        int i = 0;  // index for str1
        int j = 0;  // index for str2
        
        while (i < str1Arr.length && j < str2Arr.length) {
            if (j == -1 || str1Arr[i] == str2Arr[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        //通俗易懂的版本
        // while (i < str1Arr.length && j < str2Arr.length) {
        //     if ( str1Arr[i] == str2Arr[j]) {
        //         i++;
        //         j++;
        //     } else if (next[j] == -1) {
        //         i++;
        //     } else {
        //         j = next[j];
        //     }
        // }
        
        return j == str2Arr.length ? i - j : -1;
    }



    /**
     * 获取str2Arr 的next数组
     * @param str2Arr
     * @return
     */
    static int[] getNextArr(char[] str2Arr){

        int[] nextArr = new int[str2Arr.length];
        nextArr[0]= -1;
        nextArr[1]= 0;
        for (int i = 2; i < str2Arr.length; i++) {
            // offset的取值范围为1~i，逐个确认；最大的offset为K值; 这个值是 对应一个i下，K值的尝试
            int goForK = 0;
            // index 为i的字符，它的最长前缀和后缀匹配长度
            int k = 0;

            // K 不可以 是i前面所有的字符的长度，所以 减个1
            while (goForK++ < i -1 ) {
                // 举例说明： abbstabbef, 比如i指向了f； 当foForK 为2的时候， 那么对比的是 前缀ab 和后缀be
                // 前缀的a的index ==0； 后缀的b的index==7； 前缀的b的index ==1； 后缀的e的index==8；
                // 这里的gap就是 前缀的a与后缀的b，前缀的b和后缀的e 之间的距离：7
                // 这个gap = f字符的index 9 - foForK的2 = 7
                int gap = i-goForK;
                // 当次尝试的goForK，默认ok；如果在前缀和后缀对比过程中，有一个字符对应不上，该次尝试即为失败
                boolean goodTry = true;

                for (int j = 0; j < goForK; j++) {
                    if (str2Arr[j] != str2Arr[j + gap]){
                        goodTry = false;
                        break;
                    }
                }

                if (goodTry) {
                    k = Math.max(k,goForK);
                }


//                if (str2Arr[goForK] == str2Arr[i-goForK-1]) {
//                    goForK ++;
//                } else {
//                    break;
//                }
            }
            nextArr[i] = k;
        }
        return nextArr;
    }

    /**
     * 优化版本：获取str2Arr的next数组
     * 利用已计算的next值来优化计算过程，减少计算量
     * 这里的整体思路为  基于i-1位置的next值，计算i位置的next值
     * @param str2Arr 待处理的字符数组
     * @return next数组，记录每个位置的最长前缀和后缀匹配长度
     */
    static int[] getNextArrOptimized(char[] str2Arr) {
        if (str2Arr == null || str2Arr.length == 0) {
            return new int[0];
        }
        
        int[] nextArr = new int[str2Arr.length];
        nextArr[0] = -1;  // 第一个字符的next值固定为-1
        if (str2Arr.length == 1) {
            return nextArr;
        }
        
        nextArr[1] = 0;   // 第二个字符的next值固定为0
        // i位置的next值(K值)，即表示i的next值，也表示i位置要与str2Arr[cn]位置的字符进行比较
        int cn = 0;       // cn表示当前要比较的字符的位置
        int i = 2;        // 从第三个字符开始计算
        
        while (i < str2Arr.length) {
            if (str2Arr[i - 1] == str2Arr[cn]) {
                // 如果前一个字符与cn位置的字符相等
                // 则当前位置的最长匹配长度为cn+1
                nextArr[i++] = ++cn;
            } else if (cn > 0) {
                // 如果不相等，且cn>0，则回溯到next[cn]继续比较
                cn = nextArr[cn];
            } else {
                // 如果cn已经回溯到0仍不相等，则当前位置的最长匹配长度为0
                nextArr[i++] = 0;
            }
        }
        return nextArr;
    }
    

    public static void main(String[] args) {
        final String str1 = "mnababstababqfz";
        final String str2 = "ababq";
        System.out.println(Arrays.toString(getNextArr(str2.toCharArray())));
        System.out.println(Arrays.toString(getNextArrOptimized(str2.toCharArray())));
        System.out.println(indexOf(str1, str2));
        System.out.println(indexOf2(str1, str2));
    }
}
